package com.mccken.practice.top100.Top_1$20.Top_29;

import com.mccken.practice.top100.ListNode;
import com.mccken.practice.top100.ListNodeUtil;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-02-24 22:39
 **/
public class ReverseGroup {

	public ListNode reverseKGroup(ListNode head, int k) {
		ListNode hair = new ListNode(0);
		// pre.next 就是需要返回的头结点
		ListNode pre = hair;
		pre.next = head;

		while (head != null) {
			ListNode tail = pre;
			for (int i = 0; i < k; i++) {
				tail = tail.next;
				if (tail == null) {
					return hair.next;
				}
			}

			ListNode nex = tail.next;

			ListNode[] nodes = myReverse(head, tail);
			head = nodes[0];
			tail = nodes[1];

			pre.next = head;
			tail.next = nex;

			pre = tail;
			head = tail.next;
		}
		return hair.next;
	}

	private ListNode[] myReverse(ListNode head, ListNode tail) {

		ListNode p = head;
		ListNode prev = tail.next;
		
		while (prev != tail) {
			ListNode nex = p.next;
			p.next = prev;
			prev = p;
			p = nex;
		}
		
		return new ListNode[]{tail, head};
	}

	public static void main(String[] args) {
		ListNode head = ListNodeUtil.buildListNode(new int[]{1,2,3,4,5});
		
		ReverseGroup temp = new ReverseGroup();
		ListNode listNode = temp.reverseKGroup(head, 2);
		ListNodeUtil.printListNode(listNode);

	}

}
